Searching for Bayesian Network Structures in the Space of Restricted Acyclic Partially Directed Graphs

摘要

Although many algorithms have been designed to construct Bayesian networkstructures using different approaches and principles, they all employ only twomethods: those based on independence criteria, and those based on a scoringfunction and a search procedure (although some methods combine the two). Withinthe score+search paradigm, the dominant approach uses local search methods inthe space of directed acyclic graphs (DAGs), where the usual choices fordefining the elementary modifications (local changes) that can be applied arearc addition, arc deletion, and arc reversal. In this paper, we propose a newlocal search method that uses a different search space, and which takes accountof the concept of equivalence between network structures: restricted acyclicpartially directed graphs (RPDAGs). In this way, the number of differentconfigurations of the search space is reduced, thus improving efficiency.Moreover, although the final result must necessarily be a local optimum giventhe nature of the search method, the topology of the new search space, whichavoids making early decisions about the directions of the arcs, may help tofind better local optima than those obtained by searching in the DAG space.Detailed results of the evaluation of the proposed search method on severaltest problems, including the well-known Alarm Monitoring System, are alsopresented.